package com.shirley.algorithm.sort;

import java.util.Arrays;


public class QuickSort extends SortBase {

    public static int[] sort(int[] source) {
        int[] arr = Arrays.copyOf(source, source.length);
        return quickSort(arr, 0, arr.length);
    }

    private static int[] quickSort(int[] arr, int left, int right) {
        int povit = left;
        int index = left + 1;
        if (left >= right) {
            return arr;
        }

        for (int i = index; i < right; i++) {
            if (arr[i] < arr[povit]) {
                swap(arr, index, i);
                index++;
            }
        }

        if (povit < index - 1) {
            swap(arr, povit, index - 1);
            povit = index - 1;
        }

        quickSort(arr, left, povit);
        quickSort(arr, povit + 1, right);
        return arr;

    }
}
